package 系统复习.回溯算法;


import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
 * candidates 中的每个数字在每个组合中只能使用 一次 。
 */
public class L40 {

    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    int sum = 0;

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {

        Arrays.sort(candidates);
        backtracking(candidates, target, 0);
        return result;

    }

    private void backtracking(int[] candidates, int target, int startIndex) {

        if (sum > target) {
            return;
        }
        if (sum == target) {
            result.add(new ArrayList<>(path));
            return;
        }

        for (int i = startIndex; i < candidates.length; i++) {
            // 使用 i > startIndex 来判断是否是一个分支内
            if (i > startIndex && candidates[i - 1] == candidates[i] ) {
                continue;
            }
            path.add(candidates[i]);
            sum += candidates[i];
            backtracking(candidates, target, i + 1);
            sum -= candidates[i];
            path.remove(path.size() - 1);

        }

    }


    public static void main(String[] args) {

        L40 l40 = new L40();
        List<List<Integer>> lists = l40.combinationSum2(new int[]{2,5,2,1,2}, 5);
        lists.forEach(list -> {
            list.forEach(System.out::print);
            System.out.println();
        });

    }
}
